package DataStructureAndAlgorithm.Tedukuri.位运算;
import java.util.Scanner;
import java.util.Arrays;

//状态压缩
public class AcWing_91 {
    static int N = 20;
    static int[][] weight = new int[N][N];
    //dp[i][j]：表示经过点的状态对应的二进制为1，且目前处于j点的最短路径
    //默认被访问过的点的状态为1，未访问为0
    static int[][] dp = new int[1 << N][N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                weight[i][j] = in.nextInt();
            }
        }
        //初始化所有的路径长度为无穷大
        for (int i = 0; i < 1 << N; i++)Arrays.fill(dp[i],9999999);
        //在原点默认为路径为0
        dp[1][0] = 0;
        //枚举每种经过点的所有状态对应的二进制数
        for (int i = 1; i < (1 << n); i++){
            for (int j = 0; j < n; j++){
                //判断是否已经走到j点
                if (((i >> j) & 1) == 1){
                    //到达j点走，枚举所有从k走到j点的状态
                    for (int k = 0; k < n; k++){
                        //判断是否可以从k点走到j点
                        if ((((i - (1 << j)) >> k) & 1) == 1){
                            //如果能从k点到达j点，则更新dp[i][j]
                            dp[i][j] = Math.min(dp[i][j],dp[i - (1 << j)][k] + weight[k][j]);
                        }
                    }
                }
            }
        }
        //(1<<n)-1：即得到二进制数为n个1的数
        System.out.print(dp[(1 << n) - 1][n - 1]);
    }
}
/*
给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1

的最短 Hamilton 路径。

Hamilton 路径的定义是从 0
到 n−1

不重不漏地经过每个点恰好一次。
输入格式

第一行输入整数 n

。

接下来 n
行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]

）。

对于任意的 x,y,z
，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]

。
输出格式

输出一个整数，表示最短 Hamilton 路径的长度。
数据范围

1≤n≤20

0≤a[i,j]≤107

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

 */